翻訳と辞書 Words near each other ・ Arita Station ・ Arita, Saga ・ Aritaki Arboretum ・ Aritao ・ Aritar, Sikkim ・ Aritatsu Ogi ・ Arith ・ ARITH Symposium on Computer Arithmetic ・ ARITH-MATIC ・ Aritha Van Herk ・ Arithmancy ・ Arithmaurel ・ Arithmetic ・ Arithmetic (song) ・ Arithmetic and geometric Frobenius ・ Arithmetic circuit complexity ・ Arithmetic coding ・ Arithmetic combinatorics ・ Arithmetic derivative ・ Arithmetic dynamics ・ Arithmetic for Parents ・ Arithmetic function ・ Arithmetic genus ・ Arithmetic group ・ Arithmetic hyperbolic 3-manifold ・ Arithmetic IF ・ Arithmetic logic unit ・ Arithmetic mean ・ Arithmetic number ・ Arithmetic of abelian varieties Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Arithmetic circuit complexity ： ウィキペディア英語版 Arithmetic circuit complexity In computational complexity theory, ''arithmetic circuits'' are the standard model for computing polynomials. Informally, an arithmetic circuit takes as inputs either variables or numbers, and is allowed to either add or multiply two expressions it already computed. Arithmetic circuits give us a formal way for understanding the complexity of computing polynomials. The basic type of question in this line of research is `what is the most efficient way for computing a given polynomial f?'. == Definitions == An ''arithmetic circuit'' C over the field F and the set of variables x1,...,xn is a directed acyclic graph as follows. Every node in it with indegree zero is called an ''input gate'' and is labeled by either a variable xi or a field element in F. Every other gate is labeled by either + or $\backslash times$; in the first case it is a ''sum'' gate and in the second a ''product'' gate. An ''arithmetic formula'' is a circuit in which every gate has outdegree one (and so the underlying graph is a directed tree). A circuit has two complexity measures associated with it: size and depth. The ''size'' of a circuit is the number of gates in it, and the ''depth'' of a circuit is the length of the longest directed path in it. For example, the circuit in the figure has size six and depth two. An arithmetic circuit computes a polynomial in the following natural way. An input gate computes the polynomial it is labeled by. A sum gate v computes the sum of the polynomials computed by its children (a gate u is a ''child'' of v if the directed edge (u,v) is in the graph). A product gate computes the product of the polynomials computed by its children. Consider the circuit in the figure, for example: the input gates compute (from left to right) x1,x2 and 1, the sum gates compute x1 + x2 and x2 + 1, and the product gate computes (x1 + x2)x2(x2 + 1). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Arithmetic circuit complexity」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.